#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;
//class Solution {
//public:
//    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int vF, int Price, int Dist) {
//        vector<int>v;
//        int n = restaurants.size();
//        for (int i = 0; i < n; i++) {
//            vector<int>& e = restaurants[i];
//            if (e[3] <= Price && e[4] <= Dist && e[2] >= vF) {
//                v.push_back(i);
//            }
//        }
//        sort(v.begin(), v.end(), [&](int& a, int& b)->bool {
//            vector<int>& v1 = restaurants[a];
//            vector<int>& v2 = restaurants[b];
//            return v1[1] > v2[1] || (v1[1] == v2[1] && v1[0] > v2[0]);
//            });
//        vector<int>ans(v.size());
//        for (int i = 0; i < v.size(); i++) {
//            ans[i] = restaurants[v[i]][0];
//        }
//        return ans;
//    }
//};


class Solution {
public:
    typedef long long LL;
    bool check(vector<int> v, int r, int k, LL m) {
        int n = v.size();
        LL s = accumulate(v.begin(), v.begin() + (r + 1 > n ? n : r + 1), 0LL);
        LL cnt = 0;
        for (int i = 0; i < n; i++) {
            if (s < m) {
                cnt += m - s;
                v[(i + r < n ? i + r : n - 1)] += m - s;
                s = m;
            }
            s += ((i + r + 1 < n ? v[i + r + 1] : 0) - (i - r < 0 ? 0 : v[i - r]));
        }
        return cnt <= k;
    }
    long long maxPower(vector<int>& stations, int r, int k) {
        LL left = *min_element(stations.begin(), stations.end());
        LL right = accumulate(stations.begin(), stations.end(), 0LL) + k;
        while (left <= right) {
            LL mid = left + (right - left) / 2;
            if (check(stations, r, k, mid)) left = mid + 1;
            else right = mid - 1;
        }
        return right;
    }
};
int main()
{
    vector<int> arr = { 4,4,4,4 };
    cout << Solution().maxPower(arr,0,3);
    return 0;
}